package Medium;

import java.util.Arrays;

public class LC2300 {
    public static int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length, m = potions.length;
        int[] nPairs = new int[n];
        for (int i = 0; i < n; i++) {
            int spell = spells[i];
            int minPotionPower = (int) Math.ceil(success * 1.0 / spell);
            if (minPotionPower > potions[m - 1]) nPairs[i] = 0;
            else if (minPotionPower <= potions[0]) nPairs[i] = m;
            else {
                int left = 0, right = m, mid;
                while (left < right) {
                    mid = (int) ((long) left + right) / 2;
                    if (potions[mid] == minPotionPower) {
                        while (mid - 1 >= 0 && potions[mid - 1] == potions[mid]) mid--; // 处理药水魔力重复的情况
                        nPairs[i] = m - mid;
                        break;
                    }
                    else if (potions[mid] < minPotionPower) left = mid + 1;
                    else right = mid;
                }
                // left==right，且target在nums[left-1]和nums[left]之间
                if (left >= right) nPairs[i] = m - left;
            }
        }

        return nPairs;
    }

    public static void main(String[] args) {
        int[] spells = new int[]{5, 1, 3};
        int[] potions = new int[]{1, 2, 3, 4, 5};
        long success = 7;
        System.out.println(successfulPairs(spells, potions, success));
    }
}
